'''
Created on Aug 30, 2012

@author: anupam saini
'''


from com.anupam.common.utils import Utils

class StackCustom(list):
  """ Modifying List to act as a stack."""

  def __init__(self):
    list.__init__(self)

  def insert(self, *args, **kwargs):
    raise NotImplementedError

  def remove(self, *args, **kwargs):
    raise  NotImplementedError

  def extend(self, *args, **kwargs):
    raise NotImplementedError

  def top(self):
    """ Fetch and return the top element of the stack.
    """
    value = None
    try:
      value = self.pop()
      self.append(value)
    except IndexError:
      pass
    return value

  def is_empty(self):
    """ Checks if the stack is empty.
    """
    if len(self):
      return False
    return True

  def test(self):
    """ Useless method, here for the lack of test case."""

    print self.is_empty()
    self.append(1)
    print self.is_empty()
    print self.top()
    print self.is_empty()
    print self.pop()
    print self.is_empty()

class ConstantTimeStack(object):
  """Performs push, pop and fetching min value in stack in O(1) time."""

  def __init__(self, min_stack=StackCustom(), data_stack=StackCustom()):
    """ Creates an instance.
    
    Args:
      min_stack: stack plain vanilla stack holding the min values at a
        particular index. It's size can be less then data_stack.
      data_stack: Stack holding all the pushed elements.
    """
    self.min_stack = min_stack
    self.data_stack = data_stack

  def push(self, value):
    self.data_stack.append(value)
    if self.min_stack.is_empty() or self.min_stack.top() >= value:
        self.min_stack.append(value)
  
  def pop(self):
    if self.data_stack.is_empty():
      return
    if self.min_stack.top() == self.data_stack.top():
      self.min_stack.pop()
    return self.data_stack.pop()
  
  def min(self):
    if self.min_stack.is_empty():
      return
    return self.min_stack.top()

def main():
  constTimeStack = ConstantTimeStack()
  numbers = Utils().generateNumbers(5)
  print 'generated stack %s ' % numbers
  for number in numbers:
    constTimeStack.push(number)
  
  for number in numbers:
    print 'min value %s ' % constTimeStack.min()
    print 'poped value %s ' % constTimeStack.pop()

if __name__ == "__main__":
  #StackCustom().test()
  main()

